課程名稱 |
高等演算法 Advanced Algorithms |
開課學期 |
112-2 |
授課對象 |
電機資訊學院 電機工程學研究所 |
授課教師 |
陳和麟 |
課號 |
EE5182 |
課程識別碼 |
921 U2590 |
班次 |
|
學分 |
3.0 |
全/半年 |
半年 |
必/選修 |
選修 |
上課時間 |
星期五2,3,4(9:10~12:10) |
上課地點 |
明達231 |
備註 |
總人數上限:180人 |
|
|
課程簡介影片 |
|
核心能力關聯 |
本課程尚未建立核心能力關連 |
課程大綱
|
為確保您我的權利,請尊重智慧財產權及不得非法影印
|
課程概述 |
本校同學希望旁聽課程請直接聯絡助教吳政宏 r11921036@ntu.edu.tw
In this course, we will study various techniques for designing and analyzing algorithms. We will mainly focus on problems for which the exact algorithm is not known or not efficient enough and problems with resource constraints. Besides designing efficient algorithms, proving the performance guarantees is also a main topic of this course.
In the first half of the semester, we will focus on approximation algorithms. Approximation algorithms are algorithms that find near-optimal solutions with provable performance guarantees in polynomial time. We will cover design techniques such as rounding and primal-dual algorithms.
In the second half of the semester, we will focus on different topics in randomized algorithms. We will cover algorithm design techniques such as hashing, sampling, random walks, and derandomization.
|
課程目標 |
本課程主要針對從事演算法研究的學生,提供演算法設計的技巧與未來學習的方向。 |
課程要求 |
預修課程: 演算法、機率、離散數學、資料結構 |
預期每週課後學習時數 |
|
Office Hours |
每週四 10:00~12:00 每週三 10:00~12:00 每週五 12:00~13:00 備註: TA office hours:
吳政宏, email: r11921036@ntu.edu.tw, office hour: Wed 10:00-12:00 MD709
李怡萱, email: r12921065@ntu.edu.tw, office hour: Thu 10:00-12:00 MD709 |
指定閱讀 |
|
參考書目 |
Approximation Algorithms, Vazirani
Design of Approximation Algorithms, Williamson and Shmoys
Randomized Algorithms, Motwani and Raghavan
|
評量方式 (僅供參考) |
No. |
項目 |
百分比 |
說明 |
1. |
作業 |
40% |
約四次手寫作業 |
2. |
期中考 |
35% |
|
3. |
期末考 |
25% |
|
|
針對學生困難提供學生調整方式 |
上課形式 |
以錄影輔助 |
作業繳交方式 |
|
考試形式 |
|
其他 |
由師生雙方議定 |
|
週次 |
日期 |
單元主題 |
第0週 |
|
*** 進度視教學狀況隨時調整 *** |
第01週 |
2/23 |
Course Overview, Knapsack Problem, PTAS/FPTAS |
第02週 |
3/1 |
Approximation Algorithms: Subset Sum, Bin Packing |
第03週 |
3/8 |
Linear Programming, ILP, LP-Relaxation |
第04週 |
3/15 |
Duality |
第05週 |
3/22 |
Primal-Dual Algorithms |
第06週 |
3/29 |
Greedy and Local Search Algorithms |
第07週 |
4/5 |
No class (spring break) |
第08週 |
4/12 |
Local Search Algorithms, Homework Solutions |
第09週 |
4/19 |
Midterm Exam (covering week 1 - week 8) |
第10週 |
4/26 |
Randomized Algorithm, Derandomization |
第11週 |
5/3 |
Hashing |
第12週 |
5/10 |
Markov Chain, Random Walk |
第13週 |
5/17 |
Counting and Sampling |
第14週 |
5/24 |
Counting, Homework Solutions |
第15週 |
5/31 |
Online Algorithms, Streaming Algorithms (Videos from last year's lectures only) |
第16週 |
6/7 |
Final Exam (covering week 10 - week 14) |
|